import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/18 10:40
 * @description 哈希标存储所有节点的父节点，因为题目给定所有Node.val 互不相同
 */
public class Solution3 {
    public static void main(String[] args) {

    }
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        // 从p开始逐渐往父节点移动，并记录访问过的父节点
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            // 一旦有祖先被访问过，那么说明为两个节点的最近公共祖先
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
}
